package everyday;

import org.junit.jupiter.api.Test;

import java.sql.Array;
import java.util.*;

/**
 * @Author: Siantar
 * @Date: 2023-05-28-0:10
 * @Description: 1.0
 */
public class T1439 {
    public int kthSmallest(int[][] mat, int k) {
        int m = mat.length;
        int[] prev = mat[0];
        for (int i = 1; i < m; i++) {
            prev = merge(prev, mat[i], k);
        }
        return prev[k-1];
    }

    public int[] merge(int[] f, int[] g, int k) {
        if (f.length < g.length) {
            return merge(g, f, k);
        }

        Queue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        for (int i = 0; i < g.length; i++) {
            queue.offer(new int[]{0, i, f[0] + g[i]});
        }
        List<Integer> list = new ArrayList<>();
        while (k > 0 && !queue.isEmpty()) {
            int[] p = queue.poll();
            list.add(p[2]);
            if (p[0] + 1 < f.length) {
                queue.offer(new int[]{p[0] + 1, p[1], f[p[0] + 1] + g[p[1]]});
            }
            k--;
        }
        return list.stream().mapToInt(a->(int)a).toArray();
    }

    @Test
    public void test() {
        System.out.println(kthSmallest(new int[][]{{1, 3, 11}, {2, 4, 6}}, 5));
    }
}
